package algorithms.search;

/**
 * (基于无序链表)链表实现的符号表
 * @author glogo
 *
 * @param <Key>
 * @param <Value>
 */
public class SequentialSearchST<Key, Value> {

	private Node first;
	private int N = 0;	
	
	private class Node{
		Key key;
		Value value;
		Node next;
		public Node(Key key, Value value, Node next) {
			this.key   = key;
			this.value = value;
			this.next  = next;
		}
	}
	
	
	public Value get(Key key){
		for(Node x = first; x != null; x = x.next)
			if(key.equals(x.key))	return x.value;
		return null;
	}
	
	public void put(Key key, Value value){
		for(Node x = first; x != null; x = x.next)
			if(key.equals(x.key)){
				x.value = value;
				return;
			}
		first = new Node(key, value ,first);
		N++;
	}
	
	public int size(){	return N;	}
	
	
	public boolean contains(Key key){
		return get(key) != null;
	}
	
	public void delete(Key key){
		first = delete(first, key);
	}
	
	private Node delete(Node x, Key key){
		if(x == null)	return null;
		if(x.key.equals(key)){
			Node t = x.next;
			N--;
			return t;
		}
		x = delete(x.next, key);
		return x;
	}
	
	public Iterable<Key> keys()  {
        Queue<Key> queue = new Queue<Key>();
        for (Node x = first; x != null; x = x.next)
            queue.enqueue(x.key);
        return queue;
    }
}
